/*
https://leetcode-cn.com/problems/prefix-and-suffix-search/solution/qian-zhui-he-hou-zhui-sou-suo-by-leetcode/
 */
public class Solution745 {

    static class Trie{
        Trie[] children=new Trie[27];
        int weight=0;
    }

    Trie trie=new Trie();

    public Solution745(String[] words) {
        for (int i=0;i<words.length;i++){
            String target=words[i].concat("{");
            for (int j=0;j<target.length();j++){
                Trie node=trie;
                node.weight=i;
                for (int k=j;k<target.length()*2-1;k++){
                    int p=target.charAt(k%target.length())-'a';
                    if (node.children[p]==null){
                        node.children[p]=new Trie();
                    }
                    node=node.children[p];
                    node.weight=i;
                }
            }
        }
    }

    public int f(String prefix, String suffix) {
        Trie node=trie;
        String target=suffix.concat("{").concat(prefix);
        for (char c : target.toCharArray()) {
            if (node.children[c-'a']==null){
                return -1;
            }
            node=node.children[c-'a'];
        }
        return node.weight;
    }

    public static void main(String[] args) {
        Solution745 solution745=new Solution745(new String[]{"apple"});
        System.out.println(solution745.f("a","e"));
    }
}
